Code and Notes (Week 1 Thursday)

module SecondLecture where

import Data.Char (toLower)
import Data.List (sort, sortOn, group)

-- A bit more syntax
-- Higher-order functions (map)

{- Functions are first-class citizens:
    functions are values same as Ints or Bools
    they can be passed to functions,
    returned from functions,
    stored in "variables"...
 -}

square :: Int -> Int
square x = x*x

quadruple :: Int -> Int
quadruple x = x*x*x*x

quadruple2 :: Int -> Int
quadruple2 x = square(square x)
-- quadruple2 is an instance of a general
-- pattern that we can abstract:
--   applying another function twice

{- generics (in things like Java)
   Haskellers just call this Polymorhism

   instead of giving a concrete type,
   we can give a *type variable*
 -}
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f(f x)
{- Lower-case names occuring types are *type variables*
   Names for concrete types are always Capital Case
 -}

applyTwice2 :: (a -> a) -> a -> a
applyTwice2 f = f . f
{- . is *function composition*

     (f . g)(x) = f(g(x))

   Why would applyTwice2 be better?
   - it's at a higher conceptual level of abstraction
   - Haskellers are really obsessed with
      point-free style:
     they like not actually writing out function
     arguments if possible
 -}


quadruple3 :: Int -> Int
quadruple3 x = applyTwice square x
{- because quadruple3 is an Int -> Int
   the type of    quadruple3 x
   is  Int
   therefore, on the RHS we need to give
     an Int
 -}

quadruple4 :: Int -> Int
quadruple4 = applyTwice square

quadruple5 :: Int -> Int
quadruple5 = \x -> applyTwice square x

applyTwiceToFive :: (Int -> Int) -> Int
applyTwiceToFive f = applyTwice f 5
{- quadruple4 has type Int -> Int
   therefore, the RHS of this declaration
   must also have type Int -> Int
 -}

{- eta properties:

     a function f, which given x returns g(x)
     is the same thing as g

     Let f(x) = g(x)

      f(2) = g(2)

     We consider functions to be *equal* if
     they behave the same on all inputs
 -}

{-   map f [a,b,c]  =   [f a, f b, f c]

     λ> map succ [1,2,3,54]
     [2,3,4,55]

     λ> map (\x -> x `mod` 2 == 0) [1,2,3,5,6,7]
     [False,True,False,False,True,False]

     Lambdas or anonymous functions

        (\x -> E)   <-- is a function which given
                        an argument x
                        returns E
 -}

x = map (\x -> x `mod` 2 == 0) [1,2,3,5,6,7]
-- Word frequency counter

{- Q: when is this x evaluated?
   A: when it's demanded (Haskell is lazy)
 -}
y = 2 `div` 0

z = False && y == 2

w = y == 2 && False

{- Q: why does Haskell allow duplicated names inside the function? For
 example, x = map (\x ...) we have both the function name x and
 argument x

   A: in this case, the outermost x is *shadowed*
      by the inner x.
      It's still in scope, but it can't be
      referred to by name
 -}

{- Typed-directed design
     we're going to start with
     a bunch of type sigs and no code
 -}

breakIntoWords :: String -> [String]
breakIntoWords = words

convertToLower :: [String] -> [String]
convertToLower = map (map toLower)

sortWords :: [String] -> [String]
sortWords = sort

-- type synonym:
-- type String = [Char]
type Run = [String]

-- groupAdjacent ["h","h","i","j","j"]
-- = [["h","h"],["i"],["j","j"]]
groupAdjacent :: [String] -> [Run]
groupAdjacent = group

sortByLength :: [Run] -> [Run]
sortByLength = reverse . sortOn length

takeLongest :: Int -> [Run] -> [Run]
takeLongest = take

generateReport :: [Run] -> String
generateReport runs =
  unwords(map individualReport runs) where
  individualReport xs =
    head xs ++ ": " ++ show(length xs)

wordFreqCounter :: Int -> String -> String
wordFreqCounter n s =
  generateReport(takeLongest n (sortByLength(groupAdjacent(
    sortWords(convertToLower(breakIntoWords s))))))

{- Now, I can test if this design is sound
   in the sense that it could possibly work
   By type checking it (because Haskell is strongly
                        typed)
 -}


{- Q: if you have Int -> String -> String how do you know if its asking
for a function (Int -> String) and gives an output String or input Int
and a function (String -> String) as output

   A: because the function arrow is right associative
           Int -> String -> String
                desugars to
           Int -> (String -> String)
      ..which is different from (Int -> String) -> String

 -}

{- Q: can we implement map ourselves?
   A: yes, with recursion
 -}

mymap :: (a -> b) -> [a] -> [b]
mymap f []     = []
mymap f (x:xs) = f x:mymap f xs

mymap2 :: (a -> b) -> [a] -> [b]
mymap2 f xs     =
  case xs of
    [] -> []
    x:xs -> f x:mymap2 f xs

myhead :: [a] -> a
myhead (x:_) = x

-- recursion: this function is calling itself
-- *pattern matching*
-- this function has not one but two defining
-- equations.
-- the one that gets used is the first one
-- that matches the shape of the input

{-  mymap succ [1,2] =
    mymap succ (1:2:[]) = (by definition)
    succ 1:mymap succ (2:[]) =
    2:mymap succ (2:[]) =
    2:succ 2:mymap succ ([]) =
    2:3:mymap succ ([]) =
    2:3:[] =

  ^ The above is *equational reasoning*
    same as in elementary maths,
    except it's about lists rather than numbers

  Haskell has an interesting property:
   Equational reasoning is *always* valid.
   If I have an expression, and I modify
   the expression by substituting equals for equals,
   the bigger expression still produces the same result.

  C does not have this property:

    suppose I know that i++ = 3

     i++ + i++ + ++i + ++i
 -}


-- dollar signs

-- pattern guards
isEven :: Int -> Bool
isEven x
 | x `mod` 2 == 0 = True
 | otherwise      = False
{- Here each clause is guarded by a
   boolean expression about the input

   The clause that gets used is the
   *first* one that is true about the input
 -}


wordFreqCounter2 :: Int -> String -> String
wordFreqCounter2 n =
  generateReport.
  takeLongest n .
  sortByLength.
  groupAdjacent.
  sortWords.
  convertToLower.
  breakIntoWords

wordFreqCounter3 :: Int -> String -> String
wordFreqCounter3 n s =
  generateReport$
  takeLongest n$
  sortByLength$
  groupAdjacent$
  sortWords$
  convertToLower$
  breakIntoWords s